﻿# 对一个元素值非零的数组排序，使得正数排在所有负数后面

##################################################################
# 解决思路：
# a.先找出第一个正数
# b.再找出排在第一个正数后的第一个负数
# c.交换这两个正数和负数
# 那么必然有以下结论：
# 1、交换后的负数的下一个数是正数，并且这个数必然是第一个正数
# 2、交换后的正数的下一个书可能是正数，也可能是负数，如果是负数，
# 那必然是排在正数后的第一个负数，因此回到步骤b，
# 如果是正数，并且是最后一个元素，那么可以结束。
##################################################################

def sort(a):
    """排序算法的实现"""
    #first_negative
    n1 = 0
    #found_negative
    found_n = False
    #first_positive
    p1 = 0
    #found_positive
    found_p = False
    
    for i in range(len(a)):
        if a[i]<0 and not found_n:
            n1 = i
            found_n = True
        if a[i]>0 and not found_p:
            p1 = i
            found_p = True
        if found_n and found_p:
            if p1<n1:
                tmp = a[n1]
                a[n1] = a[p1]
                a[p1] = tmp
                p1+=1
            found_n = False


def validate(a):
    """验证排序结果正确性"""
    is_nega = True
    for i in range(len(a)):
        if is_nega:
            is_nega = (a[i]<0)
        elif a[i]<0:
            return False
    return True


def test():
    """测试sort()算法"""
    l1 = [1, -1, -2, 2, -45, 6, 7, 8, 9, -4, -5, -6, 99]
    l2 = [-5, -6, -7, -8, 1, 2, 3, 4, -1, -2, -3, -4]
    l3 = [2, -1, -3]
    sort(l1)
    sort(l2)
    sort(l3)

